Lester Randolph Ford junior
Ne doit pas être confondu avec Lester Randolph Ford.
| Naissance | |
|---|---|
| Décès |
(à 89 ans) |
| Nationalité | |
| Formation | |
| Activité | |
| Père | |
| Mère |
Marguerite Eleanor John (d) |
| Directeur de thèse |
David G. Bourgin (d) |
|---|
Lester Randolph Ford junior (né le à Houston et mort le ) est un mathématicien américain spécialiste des problèmes des réseaux de transport. Il est le fils du mathématicien Lester R. Ford senior[1].
Il est connu pour sa contribution au problème de flot maximum : le théorème flot-max/coupe-min sur le problème de flot maximum et l'algorithme de Ford-Fulkerson pour le résoudre paraissent dans des rapports techniques en 1954 resp. 1955 et dans un périodique public en 1956 resp. 1957[2] ,[3] ,[4].
Ford a également conçu, avec Richard Bellman et Samuel End, un algorithme pour déterminer les plus courts chemins dans un graphe dont les arcs peuvent avoir des poids négatifs. Cet algorithme s'appelle maintenant l'algorithme de Bellman-Ford.
En 1959, il publie avec Selmer M. Johnson (en) un algorithme de tri par comparaisons appelé algorithme de Ford-Johnson[5]. Vingt ans plus tard seulement, il a été prouvé que cet algorithme n'est pas optimal en ce qui concerne le nombre minimum de comparaisons à effectuer[6],[7], même s'il est le meilleur pour de petites valeurs[8].
Lester Ford et Selmer Johnson ont tous deux travaillé à la RAND Corporation[1].
Notes et références
[modifier | modifier le code]- Notes
- (en) John J. O'Connor et Edmund F. Robertson, « Lester Randolph Ford », sur MacTutor, université de St Andrews..
- Lester R. Ford Jr. et Delbert R. Fulkerson, « Maximal flow through a network », Canadian Journal of Mathematics, vol. 8, , p. 399–404 (DOI 10.4153/cjm-1956-045-5, MR 0079251, lire en ligne).
- Lester R. Ford Jr. et Delbert R. Fulkerson, « A simple algorithm for finding maximal network flows and an application to the Hitchcock problem », Canadian Journal of Mathematics, vol. 9, , p. 210-218 (DOI 10.4153/CJM-1957-024-0, MR 0093427, lire en ligne).
- Saul I. Gass et Arjang A. Assad, An annotated timeline of operations research : an informal history, Kluwer Academic Publishers (Springer-Verlag), coll. « International series in operations research & management science », , 213 p. (ISBN 978-1-4020-8112-5, lire en ligne), « 1954 Max-flow min-cut theorem », p. 96-97.
- Lester R. Ford et S. M. Johnson, « A tournament problem », Am. Math. Monthly, vol. 66, no 5, , p. 387-389.
- Donald Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, , 2e éd. (ISBN 0-201-89685-0), Section 5.3.1: « Minimum-Comparison Sorting », p. 180-197.
- Glenn K. Manacher, « The Ford-Johnson algorithm is not optimal », Journal of the ACM, vol. 26, no 3, , p. 441-456.
- Marcin Peczarski, « The Ford-Johnson algorithm is still unbeaten for less than 47 elements », Information Processing Letters, vol. 101, no 3, , p. 126-128 (DOI 10.1016/j.ipl.2006.09.001).
- Sources de la traduction
- (en)/(de) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « L. R. Ford, Jr. » (voir la liste des auteurs) et en allemand « Lester Randolph Ford junior » (voir la liste des auteurs).
